\documentclass{article}
\usepackage[dutch]{babel}
\usepackage[utf8x]{inputenc}
\usepackage[font=small,format=plain,labelfont=bf,up,textfont=it,up]{caption}
\usepackage{ijcai11, times, graphicx, float, tikz, todonotes, amsmath, amsfonts, amssymb}
\usetikzlibrary{shapes}

\hyphenation{stap-lengtes}
\newcommand{\comment}[1]{}

\title{Self-Avoiding walks met alternerende staplengtes}
\author{Jonas Vanthornhout \\ \textit{jonas.vanthornhout@student.kuleuven.be}\\Departement Computerwetenschappen\\ K.U.Leuven\And Koen Van den dries\\ \textit{koen.vandendries@student.kuleuven.be} \\Departement Computerwetenschappen\\ K.U.Leuven}
\date{4 mei 2011}

\tikzstyle{node} = [circle, draw, fill=black, scale=0.2]
\tikzstyle{cloud1} = [cloud, draw, minimum size=1cm]
\tikzstyle{farnode} = [circle, draw, fill=black, scale=0.2, node distance = 28cm]

\begin{document}
\maketitle

\begin{abstract}
	Self-avoiding walks zijn al veel bestudeerd, vooral in de context voor polymeren. Maar er is weinig onderzoek gedaan naar hun gemiddelde aantal stappen. De resultaten die bestaan zijn meer dan een decennium oud en daarom relatief onnauwkeurig. Ook is een self-avoiding walk met twee verschillende staplengtes nog nooit onderzocht. Door een tweede staplengte in te voeren, ontstaat een merkwaardige overgang wanneer de twee staplengtes ongeveer gelijk zijn. Ook is het mogelijk om het gemiddeld aantal stappen van de self-avoiding walk op te drijven door eenvoudigweg de ene staplengte verwaarloosbaar klein te maken ten opzichte van de andere. \comment{Deze eigenschappen worden veroorzaakt door de volgorde waarin de staplengtes gekozen worden of door het rooster waarop de self-avoiding walk loopt.} Random of alternerend tussen de staplengtes kiezen en ook de geometrie van het rooster hebben invloed op deze eigenschappen. Er zijn dus een aantal nieuwe en vernieuwde concepten i.v.m. self-avoiding walks die ervoor kunnen zorgen dat polymeren beter gesimuleerd kunnen worden.
\end{abstract}

\section{Self-Avoiding walk}
Een \emph{self-avoiding walk} (SAW) is een speciaal geval van de random walk. Een $n$-dimensionale random walk is het pad $\mathbb{N} \to \mathbb{R}^{n}$ dat afgelegd wordt waarbij op elk moment een stap wordt gezet in een willekeurige richting. De SAW heeft nog een extra voorwaarde namelijk dat het pad zich nergens mag snijden. Dus het is niet toegestaan dat een SAW 2 keer op eenzelfde punt mag terecht komen. Het soort SAW dat in deze paper bestudeerd wordt is de \emph{growing self avoiding walk}. Hierbij laten we een pad groeien waarbij op elk tijdstip een stap wordt gezet in een willekeurige richting waarin het het pad zich niet zou snijden. De SAW kan zo vastlopen op een bepaald moment als het geen richting meer uit kan zonder zichzelf te snijden. Ook zijn onze SAWs van de vorm $\mathbb{N} \to \mathbb{Q}^{n}$. Dit is zo gekozen zodat berekeningen eenvoudiger kunnen gehouden worden. In deze paper beschouwen we als de lengte van de SAW het aantal stappen dat de SAW heeft kunnen zetten voor de SAW vastloopt. Een SAW kan vastlopen wanneer het bijvoorbeeld een rechthoek vormt en deze dan binnengaat. Doordat de kans dat een SAW blijft rondlopen klein is kunnen we een gemiddelde lengte van SAWs berekenen. Op figuur \ref{fig:min_saw} is een minimale SAW te zien. Dit is de SAW met het kleinst mogelijk aantal stappen. Op een vierkant rooster zijn dat er $7$.
\begin{figure}[H]
	\centering
	\begin{tikzpicture}[node distance = 8cm, auto]
		\node[node] (node0) {};
		\node[node, below of=node0] (node1) {};
		\node[node, right of=node1] (node2) {};
		\node[node, right of=node2] (node3) {};
		\node[node, above of=node3] (node4) {};
		\node[node, above of=node4] (node5) {};
		\node[node, left of=node5] (node6)  {};
		\node[node, below of=node6] (node7) {};
		\draw (node0) -- (node1) -- (node2) -- (node3) -- (node4) -- (node5) -- (node6) -- (node7);
	\end{tikzpicture}
	\caption{Een minimale SAW: er worden zeven stappen gezet waarin de SAW een rechthoek vormt en deze binnen gaat. Deze SAW heeft als lengte 7.}
	\label{fig:min_saw}
\end{figure}

In deze paper bestuderen we vooral SAWs die verschillende staplengtes hebben. Een SAW met als staplengtes $m$ en $n$ noemen we een $m\!-\!n$ SAW. De SAW mag dan stappen zetten met lengte $m$ en stappen met lengte $n$. Hier is self-avoiding gedefinieerd als: ``de SAW mag nooit op een vorig punt terugkomen maar mag ook nooit een zijde snijden die al vroeger gemaakt is''. De keuze of een stap van lengte $m$ of $n$ gezet wordt kan willekeurig gebeuren maar ook alternerend.

We bespreken vooral SAWs met alternerend staplengtes. Nog specifieker bekijken we vooral SAWs waarvan de ene staplengte 1 is en de andere in de buurt van 1 ligt ofwel veel groter is, zeg 500. In dit geval is het ook van belang welke stap het eerst gezet wordt. Bij ons is dat altijd de stap van lengte 1. Bijna alle door ons gesimuleerde SAWs lopen op een vierkant rooster in twee dimensies. Enkel in Sectie \ref{sec:andere_resultaten} wordt van deze voorwaarde afgeweken. Dan laten we een SAW lopen op een kubus en een hyperkubus. Ook bestuderen we kort hexagonale en triangulaire roosters.

\section{Verwant onderzoek}
De meeste papers die SAWs behandelen, onderzoeken vooral hoeveel SAWs er zijn van een bepaalde lengte. Dit probleem is namelijk NP-hard. Hier wordt dan een formule gezocht die het aantal SAWs uitzet ten opzichte van een aantal constanten. Zo heeft elk rooster een constante. We zullen verder nog zien dat onze resultaten ook te verklaren zijn door het gebruik van bepaalde roosters. Een andere vaak onderzochte eigenschap is de gemiddelde afstand tussen de twee eindpunten van de SAW.

In deze paper onderzoeken wij daarentegen iets totaal anders. Wij zijn ge\"interesseerd in hoeveel stappen een SAW gemiddeld kan zetten. In \cite{hemmer} wordt vermeld dat een SAW met staplengte \'e\'en als gemiddelde lengte $70.7 \pm 0.2$ heeft. \cite{diplomarbeit} bekomt daarentegen een gemiddelde lengte van $71.7 \pm 0.2$. Beide resultaten steunen op $60\,000$ simulaties. Het verschil tussen de twee papers is mogelijk te wijten aan de manier waarop de lengte van het pad geteld wordt: het aantal stappen of het aantal punten. Deze twee manieren van tellen hebben namelijk altijd als verschil \'e\'en. Het is dan wel merkwaardig dat de minimale lengte van een SAW bij \cite{diplomarbeit} als lengte $7$ heeft. Dit strookt namelijk niet met de manier van tellen bij de gemiddelde lengte.

\cite{hemmer} stelt ook een formule voor om de kansverdeling van de lengtes te fitten. In \cite{diplomarbeit} wordt deze formule herzien en verbeterd. Beiden vermelden ook dat de driedimensionale SAW een hogere staplengtes geeft. Enkel \cite{diplomarbeit} geeft hier een exacte waarde, namelijk $3997\pm37$. Omdat deze berekening computationeel veel zwaarder is, is ze gebaseerd op maar $10\,000$ simulaties. Net zoals \cite{diplomarbeit} bespreken wij ook het hexagonaal en triangulair rooster. \cite{diplomarbeit} vermeldt ook nog een tweedimensionaal rooster dat gebaseerd is op de sprongen van een paard uit het schaakspel. Daarnaast worden er nog meerdere driedimensionale roosters besproken.

\section{$1\!-\!1$ SAW}
\label{sec:1-1}
Wanneer we een $1\!-\!1$ SAW (dus eigenlijk een SAW met staplengte \'e\'en) krijgen we een gemiddelde lengte van $70.77 \pm 0.02$. Dit is dus een ordegrootte preciezer dan \cite{hemmer}. Onze bekomen waarde steunt dan ook op $5\,000\,000$ SAWs terwijl \cite{hemmer} zich beperkt tot $60\,000$.

Het wordt interessant als de ene staplengte niet exact \'e\'en is maar een waarde in de buurt van \'e\'en. Zo hebben we bijvoorbeeld een $1\!-\!0.99999$ en een $1\!-\!1.00001$ SAW. Hierbij valt op te merken dat een $1\!-\!0.99999$ SAW niet rechtstreeks kan berekend worden omdat er gewerkt werd op een geheel rooster. In plaats daarvan werd een $100000\!-\!99999$ SAW berekend. Deze moet dezelfde eigenschappen hebben omdat enkel het rooster herschaald werd. De gemiddelde lengte van een $1\!-\!0.99999$ SAW is $53.37 \pm 0.04$. De gemiddelde lengte van een $1\!-\!1.00001$ is $52.83 \pm 0.04$. Dit staat in schril contrast met de $70.77$ van een $1-1$ SAW. Op figuur \ref{fig:1-1} is de overgang duidelijk te zien.

\begin{figure}[H]
	\includegraphics[width = \columnwidth]{1-1}
	\caption{Gemiddelde lengtes in de buurt van een $1\!-\!1$ SAW met $e=0.00001$. Hier valt duidelijk op dat een $1\!-\!1$ SAW een uitzondering. De gemiddelde lengte van een $1\!-\!0.99999$ SAW is $53.37 \pm 0.04$, de gemiddelde lengte van een $1\!-\!1$ is $70.77 \pm 0.02$ en die van een $1\!-\!1.00001$ is $52.83 \pm 0.04$.}
	\label{fig:1-1}
\end{figure}

Een vermoedelijk verklaring hiervoor is te vinden in het feit dat een $1\!-\!0.9999$ SAW en een $1\!-\!1.0001$ SAW dichter mogen komen bij hun gemaakte pad. Een voorbeeld hiervan is te vinden op figuur \ref{fig:1-1_verklaring}. Hier staat ``L'' voor een lange stap en ``K'' voor een korte stap. Dit is een situatie die bij een $1\!-\!1$ SAW niet kan voorkomen. Bij een $1\!-\!1$ SAW zou de laatste ``K'' stap niet gezet kunnen worden. Daardoor wordt deze meer geforceerd om van zijn vorige stappen weg te lopen. De stap zou namelijk naar links of naar onder moeten gaan. Doordat hier de $1\!-\!0.9999$ SAW een stap naar boven zet, is deze dichter bij zijn vorige pad. De volgende stap heeft dus meer kans om het bestaande pad te snijden en daardoor is de kans hoger dat het pad eindigt. De situatie voor een $1\!-\!1.0001$ is analoog, maar hier is dan $1$ niet de lange stap maar de korte. Opmerkelijk hier is dat we de staplengtes zoveel mogen laten naderen tot één als we willen. Zolang er een verschil is tussen de staplengtes blijven we dit gedrag verkrijgen.

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[node distance = 12cm, auto]
		\node[cloud1] (node0) {};
		\node[node, below right of=node0, node distance=5cm] (node1) {};
		\node[node, right of=node1,  node distance = 14cm] (node2) {};
		\node[node, right of=node2] (node3) {};
		\node[node, below of=node3,  node distance = 14cm] (node4) {};
		\node[node, left of=node4] (node5) {};
		\node[node, left of=node5,  node distance = 14cm] (node6) {};
		\node[node, above of=node6] (node7) {};
		\draw (node0) -- (node1) to node {L} (node2) to node {K} (node3) to node {L} (node4) to node {K} (node5) to node {L} (node6) to node {K} (node7);
	\end{tikzpicture}
	\caption{Verklaring gemiddelde lengte $1\!-\!0.9999$. Hier is te zien dat een $1\!-\!0.9999$ dichter bij zijn gemaakte pad mag komen dan een normale $1\!-\!1$ SAW. Hierboven staat namelijk een situatie die onmogelijk kan voorkomen bij een $1\!-\!1$ SAW.}
	\label{fig:1-1_verklaring}
\end{figure}

\section{$1\!-\!\infty$ SAW}
\label{sec:1-infty}
Met een $1\!-\!\infty$ SAW bedoelen we een SAW waarvan de grote staplengte veel groter is dan de kleine. Met andere woorden de tweede staplengte gaat naar oneindig. We verwachten dat zo'n SAW een grotere gemiddelde staplengte zal hebben dan een gewone $1\!-\!1$ SAW omdat er nu gemakkelijker weggelopen kan worden van het al reeds gemaakte pad. Wanneer we dan de gemiddelde lengtes bekijken zien we dat deze stijgt met een lineaire trend. Dit is duidelijk te zien op figuur \ref{fig:1-infty_lin}. Hierbij valt wel op te merken dat de grote stap minstens tien keer groter moet zijn dan de kleine. Wanneer dit niet zo is, daalt eerst de gemiddelde lengte. Dit is dan een uitwaaier van het geval beschreven in Sectie \ref{sec:1-1}.

\begin{figure}[H]
	\centering
	\includegraphics[width = \columnwidth]{1-infty-lin}
	\caption{Gemiddelde lengtes van een $1\!-\!x$ SAW waarbij $x$ naar oneindig gaat. Hier valt duidelijk de lineaire trend op.}
	\label{fig:1-infty_lin}
\end{figure}

De verklaring waarom de gemiddelde lengte stijgt is te zien op figuur \ref{fig:1-infty_verklaring}. Dit is een plot van de kansverdeling van de lengtes van een $1\!-\!600$ SAW. Hier zien we dat er twee bulten aanwezig zijn. De eerste start ongeveer op de oorsprong. Maar ook bij lengte $1200$ valt er een tweede bult te zien. De eerste bult is er \'e\'en die altijd voorkomt. De tweede bult wordt pas goed zichtbaar wanneer deze niet meer vervat zit in de eerste bult. Dit is zo wanneer de grote staplengte groter is dan $200$. Wanneer de $x$ van de $1\!-\!x$ SAW groter wordt, verplaatst de bult zich ook naar rechts. Dit heeft dan als gevolg dat de gemiddelde lengte van de SAWs stijgt.

\begin{figure}[H]
	\centering
	\includegraphics[width = \columnwidth]{1-infty-bult}
	\caption{De verdeling van de lengtes van een $1\!-\!600$ SAW. De tweede bult is hier duidelijk te zien. Deze begint ongeveer op $1200$ wat juist het dubbele is van de grote stap.}
	\label{fig:1-infty_verklaring}
\end{figure}

Ook waarom deze bult juist op $1200$ voorkomt voor de $1\!-\!600$ SAW kunnen we verklaren. Op figuur \ref{fig:bult_verklaring} is te zien dat een SAW soms een rechthoek vormt waarvan de lengte iets groter is dan de grootste staplengte. De breedte van de rechthoek is juist de grootste staplengte. Als de SAW er dan in slaagt om deze rechthoek op de juiste manier binnen te gaan. Dan ligt de rest van het gedrag van de SAW vast. Er wordt een soort van radiatorpatroon gevormd dat bestaat uit $2 \cdot langste\,stap$ stappen. Doordat de SAW nog voor de rechthoek een pad gevormd heeft, hebben we een bult die begint juist na $1200$. Wanneer we deze redenering doortrekken zouden we ook een rechthoek moeten kunnen vormen met als breedte $2\cdot langste\,stap$. Met als gevolg dat we een bult moeten zien op $2400$. Helaas is deze bult niet te herkennen wanneer we $5\,000\,000$ SAWs berekenen.

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[node distance = 1.5cm, auto]
		\node[cloud1] (node0) {};
		\node[node, below right of=node0, node distance=5cm] (node1) {};
		\node[farnode, right of=node1] (node2) {};
		\node[node, below of=node2] (node3) {};
		\node[farnode, below of=node3] (node4) {};
		\node[node,  below of=node4] (node5) {};
		\node[farnode, left of=node5] (node6) {};
		\node[node, above of=node6] (node7) {};
		\node[farnode, above of=node7] (node8) {};
		\node[node, right of=node8] (node9) {};
		\node[farnode, below of=node9] (node10) {};
		\node[node, right of=node10] (node11) {};
		\node[farnode, above of=node11] (node12) {};
		\node[node, right of=node12] (node13) {};
		\node[farnode, below of=node13] (node14) {};
		\node[node, right of=node14] (node15) {};
		\node[farnode, above of=node15] (node16) {};
		\node[node, right of=node16] (node17) {};
		\node[farnode, below of=node17] (node18) {};
		\node[node, right of=node18] (node19) {};
		\node[farnode, above of=node19] (node20) {};
		\node[node, right of=node20] (node21) {};
		\node[farnode, below of=node21] (node22) {};
		\node[node, right of=node22] (node23) {};
		\node[farnode, above of=node23] (node24) {};
		\node[node, right of=node24] (node25) {};
		\node[farnode, below of=node25] (node26) {};
		\node[node, right of=node26] (node26a) {};
		\node[farnode, above of=node26a] (node26b) {};
		\node[node, right of=node26b] (node27) {};
		\node[farnode, below of=node27] (node28) {};
		\node[node, right of=node28] (node29) {};
		\node[farnode, above of=node29] (node30) {};
		\node[node, right of=node30] (node31) {};
		\node[farnode, below of=node31] (node32) {};
		\node[node, right of=node32] (node33) {};
		\node[farnode, above of=node33] (node34) {};
		\node[node, right of=node34] (node35) {};
		\node[farnode, below of=node35] (node36) {};
		\node[node, right of=node36] (node36a) {};
		\node[farnode, above of=node36a] (node36b) {};
		\node[node, right of=node36b] (node37) {};
		\node[farnode, below of=node37] (node38) {};
		\node[node, right of=node38] (node39) {};
		\node[farnode, above of=node39] (node40) {};

		\draw (node0.center) -- (node1) -- (node2) -- (node3) -- (node4) -- (node5) -- (node6) -- (node7) -- (node8) -- (node9) -- (node10) -- (node11) -- (node12) -- (node13) -- (node14) -- (node15) -- (node16) -- (node17) -- (node18) -- (node19) -- (node20) -- (node21) -- (node22) -- (node23) -- (node24) -- (node25) -- (node26) -- (node26a) -- (node26b) -- (node27) -- (node28) -- (node29) -- (node30) -- (node31) -- (node32) -- (node33) -- (node34) -- (node35) -- (node36) -- (node36a) -- (node36b) -- (node37) -- (node38) -- (node39) -- (node40);
	\end{tikzpicture}
	\caption{Verklaring tweede bult. De SAW maakt eerst een rechthoek met als breedte de langste stap, de hoogte is de langste stap + twee kleine stappen. Wanneer deze rechthoek gemaakt is gaat de SAW deze binnen. Vanaf het moment dat dit gebeurt ligt het verloop van de SAW vast. De SAW moet dan een radiatorpatroon volgen. Deze rechthoek bevat ongeveer tweemaal de grootste stap stappen.}
	\label{fig:bult_verklaring}
\end{figure}

De vergelijking van de lineair fit op figuur \ref{fig:1-infty_lin} is $l(x)=0.225032x+78.2219$. We kunnen ook bekijken hoe deze formule presteert in het voorspellen van de gemiddelde lengte. Bovenstaande formule maakt gebruik van $1\!-\!10$ SAWs tot en met $1\!-\!400$ SAWs. De voorspelde lengte van een $1\!-\!600$ SAW is dan $213.241$ terwijl de gesimuleerde waarde $212.6$ is. Dit is dus maar een fout van $0.3015\%$.

%Het is ook mogelijk om de $1\!-\!\infty$ SAW te beschrijven als een $1\!-\!x$ met waarbij $x$ naar $0$ nadert. Zoals al reeds vermeld mogen we het rooster herschalen zonder dat de eigenschappen van de SAW veranderen.

\section{Even-Oneven}
Gelijkaardig aan \cite{hemmer} en \cite{diplomarbeit} willen we een formule vinden om deze bulten te beschrijven. Wel maken wij een onderscheid dat toen niet gemaakt werd. Even en oneven lengtes beschouwen we apart. De reden hiervoor is dat het gemiddelde van de oneven lengtes sterk verschilt van het gemiddelde van de even lengtes. Dit is ook te zien in de kansverdeling van de lengtes op figuur \ref{fig:even-oneven}.

\begin{figure}[H]
	\centering
	\includegraphics[width=5cm, height= 5cm, keepaspectratio=false, trim = 7mm 0mm 90mm 0mm, clip]{1-infty-bult}
	\caption{Kansverdeling van een $1\!-\!600$ SAW. Dit is een uitvergroting voor lengtes kleiner dan 400. Hier valt dus duidelijk te zien dat er twee verschillende bulten zijn. De kleinste bult is die van de even lengtes terwijl de andere die van de oneven lengtes is.}
	\label{fig:even-oneven}
\end{figure}

Zo is bij een $1\!-\!600$ SAW de meest voorkomende even lengte 38. Deze komt zo'n 0.1358\% keer voor. De meest voorkomende oneven lengte is 41. Deze komt maar liefst 1.6878\% keer voor. Ook bekeken \cite{hemmer} en \cite{diplomarbeit} enkel de $1\!-\!1$ SAW. Aangezien op figuur \ref{fig:bult_verklaring} duidelijk te zien is dat een $1\!-\!600$ SAW nog een extra bult heeft, is logisch om voor deze bult ook een aparte fit te beschouwen. Nu is het zelfs zo dat in deze tweede bult er opnieuw een verschil is tussen even en oneven. Maar deze keer is het juist omgekeerd. Zo is de meest voorkomende even waarde groter dan 600 1218. De kans dat deze voorkomt is 0.2765\%. De meest voorkomende oneven waarde is 1243 met 0.0058\%.

Het verschil in even en oneven is bij kleine lengtes te verklaren doordat een grote stap meer kans heeft om het pad te snijden en daardoor is de kleine stap meestal de laatste. Dit komt doordat een grote stap meer ruimte inneemt en daardoor niet altijd gezet kan worden. Bij de grote lengtes is daarentegen de laatste stap vaak de grootste zoals te zien is in figuur \ref{fig:bult_verklaring}. Eigenlijk kan ook een gelijkaardige rechthoek gevormd worden maar met een oneven aantal stappen. Dit is dan een rechthoek die de SAW binnengaat maar de SAW komt er ook weer uit. Dit laat toe dat de laatste stap om het even wat mag zijn. Om zo'n rechthoek te vormen zijn er wel meer voorwaarden dan voor de rechthoek op figuur \ref{fig:bult_verklaring}. Waardoor deze veel minder voorkomt. Tenslotte is het natuurlijk van belang welke stap het eerst gebeurt: bij ons is dat de stap lengte één. Het even-oneven verschil doet zich ook voor bij de gewone $1\!-\!1$ waarbij de oneven staplengtes meer voorkomen, maar met slechts een klein verschil in frequentie. Zo komt de lengte 31 $1.17\%$ keer voor terwijl de lengte 32 $1.12\%$ keer voorkomt.

Op figuur \ref{fig:fit_klein_even} is de plot en fit te zien van een $1\!-\!600$ SAW met enkel de even lengtes kleiner dan 400. Hier valt op dat onze fit een onderschatting geeft op ongeveer 200. Bij de oneven lengtes kleiner dan 400 is deze onderschatting ook aanwezig. Dit staat op figuur \ref{fig:fit_klein_oneven}.

\begin{figure}[H]
	\centering
	\includegraphics[width = \columnwidth]{bultfitKE}
	\caption{Plot en fit van de even lengtes kleiner dan 1200 $1\!-\!600$ SAW. De fit vertoont een onderschatting bij lengtes tussen de $150$ en $200$.}
	\label{fig:fit_klein_even}
\end{figure}

\begin{figure}[H]
	\centering
	\includegraphics[width = \columnwidth]{bultfitKO}
	\caption{Plot en fit van de oneven lengtes kleiner dan 1200 $1\!-\!600$ SAW. De fit vertoont een onderschatting bij lengtes tussen de $150$ en $200$.}
	\label{fig:fit_klein_oneven}
\end{figure}

De plots en fits voor de even en oneven lengtes boven de 1200 staan respectievelijk op figuur \ref{fig:fit_groot_even} en figuur \ref{fig:fit_groot_oneven}. Deze tonen ook een lichte onderschatting juist voor 1400, alhoewel deze minder prominent is.

\begin{figure}[H]
	\centering
	\includegraphics[width = \columnwidth]{bultfitGE}
	\caption{Plot en fit van de even lengtes groter dan 1200 $1\!-\!600$ SAW.}
	\label{fig:fit_groot_even}
\end{figure}

\begin{figure}[H]
	\centering
	\includegraphics[width = \columnwidth]{bultfitGO}
	\caption{Plot en fit van de oneven lengtes groter dan 1200 $1\!-\!600$ SAW.}
	\label{fig:fit_groot_oneven}
\end{figure}

De gebruikte formule om te fitten is $ f(l) = v \left( (l-h)^{k-1} e^{\tfrac{-l}{\theta}}\right)$ waarbij waarbij $l$ de gemiddelde lengte is en $f(l)$ het aantal keer dat de lengte $l$ voorkomt. De berekende waarden voor $v,\,h,\,k,\,\theta$ voor de verschillende bulten staan in tabel \ref{tab:parameters}.

\begin{table}[H]
	\centering
	\begin{tabular}{|l|c|c|c|c|}
		\hline
		& $v$ & $h$ & $k$ & $\theta$ \\ \hline
		klein even & $390.578$ & $2.5406$ & $2.10666$ & $33.4478$ \\ \hline
		klein oneven & $3866.58$ & $3.77876$ & $2.18497$ & $33.4937$ \\ \hline
		groot even & $4e16$ & $1204$ & $1.46227$ & $40.6273$ \\ \hline
		groot oneven & $4e16$ & $1204.37$ & $2.11853$ & $33.6161$ \\ \hline
	\end{tabular}
	\caption{Parameters voor de functie $ f(l) = v \left( (l-h)^{k-1} e^{\tfrac{-l}{\theta}}\right)$}
	\label{tab:parameters}
\end{table}

Wanneer we dan deze fits gebruiken om de gemiddelde lengte van een $1\!-\!600$ SAW te berekenen bekomen we $205.4$. Terwijl  $212.6$ de effectieve waarde is. Dit is dus een fout van $-3.5\%$. Deze fout is dus te wijten aan de onderschatting die telkens gemaakt werd.

\section{Toepassingen}
Self-avoiding walks vinden hun meeste toepassingen bij het onderzoeken van polymeren. Een polymeer is een grote molecule samengesteld uit een aantal structuren die herhalend voorkomen, de zogenaamde monomeren. De meest bekende natuurlijke polymeren zijn DNA en rubber. Polymeren kunnen geproduceerd worden op natuurlijke wijze. Maar we kunnen ze ook zelf maken. Deze synthetische polymeren zijn soms ver superieur vergeleken met hun natuurlijke variant. Als we polymeren willen maken met een hoog smeltpunt moet het moleculair gewicht ook hoog liggen. Het probleem is nu dat er weinig polymeren zijn met een hoog moleculair gewicht. Dit is te zien op figuur \ref{fig:mol_gewicht}. Dus zo kunnen we self-avoiding walks gebruiken als voorspeller voor de eigenschappen van polymeren. Natuurlijk is het verre van triviaal om polymeren te maken die moeten voldoen aan vastgelegde eigenschappen. Daarom worden self-avoiding walks ook gebruikt om polymeren te simuleren. Dit is handig om berekeningen te doen met polymeren zonder zelf deze polymeren te maken zoals vermeld in \cite{polymer}.

\begin{figure}[H]
	\centering
	\includegraphics[width = \columnwidth, trim = 60mm 43mm 90mm 200mm, clip]{monoPolymer}
	\caption{Moleculair gewicht. Afbeelding uit \protect\cite{polymer}}
	\label{fig:mol_gewicht}
\end{figure}

Als we een $1\!-\!x$ SAW maken, simuleren we eigenlijk een speciaal geval van een polymeer. Namelijk een copolymeer. Dit is een polymeer dat bestaat uit een aantal verschillende monomeren. Er zijn een aantal configuraties hoe deze monomeren kunnen voorkomen. Op figuur \ref{fig:copol_alt} staat een copolymeer met twee monomeren die telkens alternerend voorkomen. Op figuur \ref{fig:copol_rand} staat opnieuw een copolymeer met twee monomeren maar deze keer komen ze voor op willekeurige posities. Er zijn nog andere configuraties mogelijk. Zo kunnen de monomeren in blokken voorkomen of kunnen er vertakkingen zijn.
\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw (0,0) .. controls (1,1) and (3,1) .. (4,0)
		\foreach \p in {0,0.25,...,1} {node[pos=\p, circle, draw, black, fill, scale=0.5]{}}
		\foreach \p in {0.125,0.375,...,1}  {node[pos=\p, diamond, draw, black, scale=0.5]{}};
		\draw (4,0) .. controls (5,-1) and (6,-1) .. (7,0)
		\foreach \p in {0,0.25,...,1} {node[pos=\p, circle, draw, black, fill, scale=0.5]{}}
		\foreach \p in {0.125,0.375,...,1}  {node[pos=\p, diamond, draw, black, scale=0.5]{}};
	\end{tikzpicture}
	\caption{
		Copolymeren met alternerende monomeren. De gebruikte monomeren zijn hier
		\protect\tikz{\protect \node[shape=diamond, draw, black, scale=0.5] {};} en
		\protect\tikz{\protect \node[shape=circle, fill, black, scale=0.5] {};}}
	\label{fig:copol_alt}
\end{figure}

\begin{figure}[H]
	\centering
	\begin{tikzpicture}
		\draw (0,0) .. controls (1,1) and (3,1) .. (4,0)
		\foreach \p in {0,0.375,0.5,0.625,1} {node[pos=\p, circle, draw, black, fill, scale=0.5]{}}
		\foreach \p in {0.125,0.25,0.75,0.875}  {node[pos=\p, diamond, draw, black, scale=0.5]{}};
		\draw (4,0) .. controls (5,-1) and (6,-1) .. (7,0)
		\foreach \p in {0.25,0.375,0.5,0.875} {node[pos=\p, circle, draw, black, fill, scale=0.5]{}}
		\foreach \p in {0.125,0.625,0.75,1}  {node[pos=\p, diamond, draw, black, scale=0.5]{}};
	\end{tikzpicture}
	\caption{Copolymeren met random monomeren. De gebruikte monomeren zijn hier
		\protect\tikz{\protect \node[shape=diamond, draw, black, scale=0.5] {};} en
		\protect\tikz{\protect \node[shape=circle, fill, black, scale=0.5] {};}}
	\label{fig:copol_rand}
\end{figure}

Een voorbeeld van een copolymeer met alternerende monomeren is styreen-maleïnezuuranhydride dat gebruikt wordt in dienbladen volgens \cite{Britannica}.

Hier dient wel de opmerking gemaakt worden dat volgens ons bekend is er nog nooit $1\!-\!x$ SAWs gebruikt geweest zijn om copolymeren te simuleren. Volgens ons is dit wel mogelijk. Als we de staplengtes beschouwen als de afstand tussen de verschillende monomeren. Dit zou dan ook betekenen dat het maken van gewone polymeren moeilijk is omdat het probleem slecht geconditioneerd is, zoals we gezien hebben op figuur \ref{fig:1-1}. Door onzuiverheden of invloeden vanaf de buitenwereld zou bijvoorbeeld de bindingslengte lichtjes kunnen veranderen. Dit heeft dan als gevolg dat de gevormde polymeren niet ideaal zijn.

\section{Andere resultaten \& experimenten}
\label{sec:andere_resultaten}
In deze sectie bespreken we nog een aantal zaken die we onderzocht hebben maar minder in detail. Van sommige hebben we een verklaring, andere hebben resultaten maar geen verklaring. Dit zijn ook zaken die nog zeker openstaan voor verder onderzoek.

\subsection{Random}
In plaats van telkens de stappen alternerend te kiezen kunnen we ook de stappen random kiezen. De aandachtige lezer ziet dat het hier niet mogelijk is om zo'n tweede bult te cre\"eren zoals in Sectie \ref{sec:1-infty}. Wat wel opvallend is, is dat de gemiddelde lengte van een random $1\!-\!x$ SAW met $x$ groot maar $58.2$ is. Op figuur \ref{fig:rand} staan de gemiddelde lengtes van een $1\!-\!x$ SAW geplot. Zoals verwacht is de $1\!-\!1$ SAW gelijk aan zijn alternerende variant. Ook vertoont deze versie opnieuw een daling van de gemiddelde lengtes wanneer $x$ in de buurt ligt van $1$. Maar in plaats van te stijgen wanneer $x>10$ blijft de gemiddelde lengte ongeveer dezelfde. Er is schijnbaar convergentie naar de waarde $58.2$. Hieruit volgt dat de gemiddelde lengte van de random $1\!-\!1$ SAW het hoogst is. Bij deze SAW kunnen we dus spreken van een maximale gemiddelde lengte. Iets wat bij de alternerende variant onmogelijk is.

\begin{figure}[H]
	\centering
	\includegraphics[width = \columnwidth]{rand}
	\caption{Gemiddelde lengtes wanneer de staplengtes random gekozen worden. Hier valt het op dat er geen lineaire stijgende trend is wanneer de grote stap stijgt. Er is schijnbaar convergentie naar $58.2$.}
	\label{fig:rand}
\end{figure}

\subsection{Meerdere dimensies}
Het is ook interessant om te zien hoe de gemiddelde lengtes veranderen wanneer we het aantal dimensies laten toenemen. Aangezien polymeren zich ontwikkelen in driedimensionale ruimtes is het interessant om ook driedimensionale SAWs te bekijken. Met onze simulaties bekomen we een gemiddelde lengte van een SAW met staplengte \'e\'en in 3D is $3\,959.37 \pm 3.71$. De bekomen waarde in \cite{diplomarbeit} is $3997\pm37$. Dus ook hier zijn we een ordegrootte nauwkeuriger. Onze waarde steunt dan ook op $1\,000\,000$ simulaties in plaats van $10\,000$. Deze stijging is eenvoudig te verklaren. Een tweedimensionale SAW moet de omtrek van een rechthoek maken om zichzelf vast te zetten. Een driedimensionale SAW moet daarentegen het oppervlak van een balk vormen om vast te lopen. Aangezien een balk meer lijnstukken heeft dan een rechthoek is de kans kleiner dat een balk gevormd wordt. Als we werken in een vierdimensionale ruimte hebben we het probleem dat het pad extreem lang wordt. Daarom werd de maximale lengte beperkt tot tien miljoen stappen. Wanneer er 1000 SAWs berekend werden, waren er 82 die deze limiet overschreden. Wanneer dit gebeurde werd een lengte van tien miljoen aangerekend. De bekomen waarde is dus een ondergrens. Een overzicht staat in tabel \ref{tab:dim}.

\begin{table}[H]
	\centering
	\small
	\begin{tabular}{|c|c|c|c|}
		
		\hline
		Dimensie & Stappen & Simulaties & Tijdsduur\\ \hline
		2D & $70.77 \pm 0.02$  & $5\,000\,000$ & 80 s\\ \hline
		3D & $3\,959.37 \pm 3.71$ & $1\,000\,000$ & 1300 s \\ \hline
		4D & $>3\,70\,475.757 \pm 96\,085$ & $1\,000$ & 4 uur \\ \hline
	\end{tabular}
	\caption{Gemiddelde lengtes van een $1\!-\!1$ SAW wanneer de dimensie toeneemt. Hierbij valt op te merken dat een SAW in 4D begrensd werd tot tien miljoen stappen. Wanneer daar toch boven gaan werd, werd de lengte van de SAW beschouwd als tien miljoen.}
	\label{tab:dim}
\end{table}

Hier is het wellicht interessant om SAWs te berekenen in nog hogere dimensies zodat het duidelijk is welk verloop de gemiddelde lengtes vertonen.

\subsection{2 kanten groeien}
\label{subsec:2_kanten}
Het is ook mogelijk om de SAW langs twee kanten te laten groeien. Dit kan op twee manieren gedaan worden. De eerste is door een SAW te maken en dan een tweede SAW te laten starten op het beginpunt van de eerste. De tweede manier is om beide uiteinden tegelijk te maken. Door bijvoorbeeld een SAW een stap te laten zetten en dan de andere SAW een stap te laten zetten. Doordat de twee SAWs wellicht op een bepaald interageren met elkaar verwachten we dat dit ook invloed zal hebben op de gemiddelde staplengte. We verwachten dat de gemiddelde lengte hoger zal zijn dan een gewone SAW maar wellicht kleiner dan het dubbele omdat de ene SAW de andere zal beperken. Op de asymmetrische manier komen we op een gemiddelde lengte van $119.2$. Wanneer ze symmetrisch groeien is de gemiddelde lengte $120.67$. We merken dat ons vermoeden bevestigd is. Tenslotte willen we nog opmerken dat de symmetrische variant een vereenvoudigde versie is van een ge\"ent polymeer. Daar kan een polymeer op een willekeurige plaats vertakken en dit kan ook meer dan \'e\'en keer voorkomen. Hier zou nog verder onderzoek kunnen gebeuren om ge\"ente polymeren te simuleren.

\subsection{Obstakels}
Het rooster waarop de SAW loopt kunnen we ook ``vervuilen'' met obstakels. In feite is dit de algemenere vorm van hetgeen wat onderzocht wordt in Subsectie \ref{subsec:2_kanten}. Het zou mogelijk moeten zijn om een obstakel in de ruimte te plaatsen zodat de gemiddelde lengte van de SAW gelijk is aan de lengte uit Subsectie \ref{subsec:2_kanten}. Nu is het interessant om te weten wat voor vorm deze obstakels hebben. Is dit mogelijk met een vierkant? Lukt dit met convexe veelhoeken? Of is dit zelfs onmogelijk met een veelhoek? Hierbij spelen natuurlijk een groot aantal parameters een rol. Waar staat het obstakel? Hoe groot is het obstakel? Welke vorm heeft het obstakel? Hoeveel obstakels staan er op het rooster? De veelheid aan parameters maakt het onderzoek naar het effect van obstakels een stuk moeilijker. Dit is ook de reden waarom we hiervan geen interessante resultaten hebben.

\subsection{Andere geometrieën}
In plaats van de SAW andere eigenschappen te geven kunnen we ook het rooster waarop de SAW zich bevindt veranderen. In plaats van een vierkant rooster kunnen we zo een hexagonaal of driehoekig rooster kiezen. Hierbij dient wel opgemerkt te worden dat bij een hexagonaal rooster het niet triviaal is om een $1\!-\!x$ SAW te defini\"eren. Bij het driehoekig rooster merken we dat er geen verschil is tussen even en oneven zoals bij het vierkant rooster. Bij het hexagonaal rooster daarentegen is er wel een onderscheid. Maar er zijn wel vier verschillende bulten die telkens modulo vier voorkomen. De gemiddelde lengte van een $1\!-\!1$ SAW op een hexagonaal rooster is $71.14 \pm 0.30$ en op een triangulair rooster is dit $77.17 \pm 0.07$. \cite{diplomarbeit} komt respectievelijk $70.9\pm0.2$ en $77.9\pm0.7$ uit. Wat hier dus opvalt is dat op het hexagonaal rooster wij ongeveer dezelfde waarde hebben. Op het vierkant rooster en op het driehoekig rooster zijn de waarden van \cite{diplomarbeit} ongeveer 1 hoger dan de onze. Een mogelijke verklaring hiervoor zou zoals eerder vermeld een verschil in definitie van de lengte van een SAW. De lengtes van de minimale SAWs op de verschillende roosters in \cite{diplomarbeit} komen echter wel overeen met de onze. Ook het hexagonale rooster komt ongeveer overeen. In deze context is het dan wellicht interessant om eens de andere roosters die in \cite{diplomarbeit} bestudeerd worden ook eens opnieuw te beschouwen. Niet enkel de bekomen waardes zouden interessant zijn. Maar ook of er een verschil is met \cite{diplomarbeit} is wetenswaardig.

\subsection{Boundingbox van een SAW}
We kunnen ook van de SAW de boundingbox berekenen. Dit is de rechthoek die gevormd wordt door de vier meest extreme punten van de SAW. Wanneer we dit hebben kunnen we ook de densiteit van de SAW berekenen. Dit is de lengte van de SAW gedeeld door de oppervlakte van de boundingbox. De lengte van de SAW is hier niet meer het aantal gezette stappen maar de Euclidische lengte van de SAW. Zo heeft een $1\!-\!1$ SAW gemiddeld een boundingbox van oppervlakte $220$. Dit betekent dus dat een $1\!-\!1$ SAW ongeveer $\frac{1}{3}$ van zijn boundingbox opvult. De $1\!-\!2$ SAW heeft als gemiddelde aantal stappen $56.67$. De gemiddelde euclidische lengte, die de volledige lengte van een pad telt rekening houdend met de verschillende staplengtes, is $85$. Deze waarde wordt bekomen door de twee staplengtes op te tellen. Dit getal te delen door $2$ en vervolgend moet dit vermenigvuldigd worden met het gemiddeld aantal stappen. De boundingbox heeft als gemiddelde oppervlakte $352$. Deze bezet dus $\frac{1}{4}$ van zijn boundingbox. Deze trend zet zich nog verder door tot de $1\!-\!4$ SAW. Vanaf dan hebben we geen resultaten meer. Hier zou verder onderzoek nog kunnen uitwijzen of dit zich blijft verder zetten of niet.

\subsection{Een andere topologie: de torus}
In plaats van de SAW te laten lopen op een oneindig groot vierkant rooster is het ook mogelijk om hem te laten lopen op een rooster op een torus. Dit kan gesimuleerd worden door een eindig vierkant rooster waarbij de bovengrenzen doorlopen naar de ondergrenzen en omgekeerd. Dit houdt in dat er twee extra parameters zijn, namelijk de lengte en breedte van het rooster. Ook zijn de staplengtes nog belangrijker. Zo is er nu een verschil tussen een $1\!-\!1$ SAW en een $2\!-\!2$ SAW. Dit is namelijk niet het geval op een oneindig groot vierkant rooster. Het is namelijk zo dat een te kleine torus de SAW teveel zal beperken, een te grote torus zal daarentegen niet veel verschillen van een oneindig rooster. Van deze variant hebben we geen interessante gemiddelde lengtes gevonden omdat we niet de juiste combinatie van parameters hebben. Dit probleem staat dus nog zeker open voor verder onderzoek. Ook zijn wellicht andere topologie\"en zoals de bol interessant.

\subsection{Meerdere richtingen}
Verder is het mogelijk om de SAW op elke punt acht mogelijke richtingen te geven in plaats van vier zoals wij gedaan hebben. Dit is dus een vierkant rooster maar met de diagonalen erbij. Deze redenering kunnen we dan zo verder doortrekken totdat de SAW op elk punt elke richting kan uitgaan. We werken dan niet meer in een discrete ruimte maar in een continue. Dit model zou beter voldoen aan de realiteit. Helaas is het een stuk ingewikkelder te implementeren. Wellicht zou een vereenvoudigde versie hiervan ook interessante resultaten geven. Als we op de vier mogelijke richtingen kleine afwijkingen toelaten kan wellicht de gemiddelde lengte van de SAW ook veranderen. Dit is dan min of meer analoog aan wat verteld werd in Sectie \ref{sec:1-1}.

\subsection{Continue SAW in een continue ruimte}
Het meest algemene geval is wanneer de SAW en de ruimte continu zijn. Wij hebben al een $1\!-\!0.9999$ SAW bestudeerd. Maar deze beperkt zich tot $\mathbb{Q}$, we zouden dit kunnen uitbreiden tot $\mathbb{R}$. We hebben al gezien dat een minimaal verschil in staplengte gigantische verschillen kan hebben. Zo is het misschien mogelijk dat een bepaald re\"eel getal als staplengte er ook kan voor zorgen dat de gemiddelde lengte van de SAW verandert.

\subsection{Point of no return}
Verder is het ook interessant om te weten vanaf wanneer zeker is dat de SAW vastgelopen is. Een geval dat we al besproken hebben is te zien op figuur \ref{fig:bult_verklaring}. Dit geval zorgt namelijk voor heel wat rekentijd. Als het mogelijk is om te voorspellen wanneer de SAW vastloopt en welke stappen gezet zullen worden is het onderzoeken van SAW een stuk eenvoudiger. Dit is vooral van toepassing bij alternerende SAWs. Niet alleen hebben random SAWs een kortere gemiddelde lengte, ook is het moeilijker om te voorspellen welke random stappen gezet zullen worden.

\section{Conclusie}
We kunnen dus besluiten dat niet alleen de ``gewone'' SAW interessant is, maar de $1\!-\!x$ SAW vertoont ook een aantal interessante eigenschappen.

Voor de gewone $1\!-\!1$ SAW hebben we de bekende waarde bevestigd. Ook is onze waarde een ordegrootte preciezer dan de waarde die gekend is in de huidige literatuur.

De $1\!-\!x$ SAW met $x\approx 1$ heeft ook een interessante overgang bij $x = 1$. Deze overgang is te verklaren doordat een SAW zich minder snel vastloopt wanneer deze meer geforceerd wordt om weg te lopen van zijn gemaakte pad. Dit heeft als gevolg dat deze SAW slecht geconditioneerd is.

Verder hebben we ook gezien dat de gemiddelde lengte lineair stijgt met de grote staplengte. Dit fenomeen is te verklaren doordat de SAW een rechthoek vormt en in deze rechthoek begint te lopen. Dit geeft als bijkomend effect dat de kansverdeling opgesplitst wordt in meerdere bulten. Waarvan telkens een bult begint op ongeveer $n \cdot 2 \cdot x$. Dit gedrag is inherent aan het feit dat de staplengtes alternerend gekozen worden. Een random SAW vertoont dit gedrag niet. Integendeel zelfs, de random SAW heeft een schijnbare convergentie naar een waarde die zelfs lager ligt dan de gemiddelde lengte van de $1\!-\!1$ SAW.

Later hebben we gezien dat deze bulten nog eens opgesplitst kunnen worden in twee delen. De bulten met oneven lengtes en die met even lengtes. Hierbij moet wel de kanttekening geplaatst worden dat veel van deze eigenschappen afhankelijk zijn van het rooster waarop gewerkt wordt. Het triangulaire rooster vertoont geen even en oneven bulten. Het hexagonale rooster daarentegen wel, maar daar is het niet zo eenvoudig om een $1\!-\!x$ SAW goed te defini\"eren.

Aangezien er alternerende en random copolymeren bestaan is het dus nu mogelijk om beter het gedrag van deze te verklaren.

\nocite{*}

\section{Bibliografie}
\bibliographystyle{named}
\bibliography{bibliography}
\end{document}
